//最⻓递增⼦序列（medium）: https://leetcode.cn/problems/longest-increasing-subsequence/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);       // 1. 创建 dp 表 + 初始化
        int ret = 1;                // 更新结果
        for (int i = 1; i < n; i++) // 2. 填表
        {
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i])
                    dp[i] = max(dp[j] + 1, dp[i]);
            ret = max(ret, dp[i]);
        }
        // 3. 返回结果
        return ret;
    }
};

//摆动序列（medium）: https://leetcode.cn/problems/wiggle-subsequence/
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1); // 1. 创建 dp 表 + 初始化
        int ret = 1;                  // 更新最终结果
        for (int i = 1; i < n; i++)   // 2. 填写 f[i] 以及 g[i]
        {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    f[i] = max(g[j] + 1, f[i]);
                else if (nums[j] > nums[i])
                    g[i] = max(f[j] + 1, g[i]);
            }
            ret = max(ret, max(f[i], g[i]));
        } // 3. 返回结果
        return ret;
    }
};
